{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5714f704",
   "metadata": {},
   "source": [
    "# 排序\n",
    "排序：将集合中的元素按某种顺序排列的过程。比如，一个单词列表可以按字母表或长度排序；\n",
    "\n",
    "\n",
    "## 冒泡排序bubbleSort\n",
    "冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。\n",
    "    - 冒泡排序，需要进行n-1次\n",
    "    - 冒泡排序，每一次都会使得第n元素处在正确位置上【看你是升序/降序】"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6d25c3c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubblesort(alist):\n",
    "    for passnum in range(len(alist)-1,0,-1):\n",
    "        for i in range(passnum):\n",
    "            if alist[i] > alist[i+1]:\n",
    "                temp = alist[i]\n",
    "                alist[i] = alist[i+1]\n",
    "                alist[i+1] = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "968d7225",
   "metadata": {},
   "source": [
    "## 选择排序selectionSort\n",
    "1. 选择排序在冒泡排序的基础上做了改进，每次遍历列表时只做一次交换。\n",
    "2. 要实现这一点，选择排序在每次遍历时寻找最大值，并在遍历完之后将它放到正确位置上。\n",
    "3. 和冒泡排序一样，第一次遍历后，最大的元素就位；\n",
    "4. 第二次遍历后，第二大的元素就位，依此类推。\n",
    "5. 若给n个元素排序，需要遍历n-1轮，这是因为最后一个元素要到n-1轮遍历后才就位。\n",
    "\n",
    "## 插入排序insertionSort\n",
    "1.它在列表较低的一端维护一个有序的子列表，并逐个将每个新元素“插入”这个子列表。\n",
    "2.直到最后，有序子表数目=最初的父表数目，而父表数目=0.排序完成\n",
    "\n",
    "## 希尔排序shell sort\n",
    "1. 它是插入排序的改进【n此子列表插入排序+最后一次稍微有序大列表排序】\n",
    "2. 操作步骤\n",
    "    1. 按照给定步长i，选中所有间隔为i的元素组成子列表n。【n=numlist/i】\n",
    "    2. 对每个子列表都进行插入排序 ，得到有序的子列表【虽然被分为子列表，但它们位置还是在原列表上，】\n",
    "    3. 当原列表进行子列表插入完成后，原列表会变得稍微有序。\n",
    "    4. 最后对稍微有序的原列表，进行一次最终的插入排序。\n",
    "    \n",
    "    \n",
    "## 并归排序mergeSort\n",
    "\n",
    "1. 并购排序思想——分治策略【改良的排序思想】\n",
    "2. 并归排序是递归算法\n",
    "    1. 它每一次都将一个列表一分为二。【当列表只有0/1个元素就认为它是有序】-基本情况\n",
    "    2. 如果列表，元素大于1，则继续对她二分。\n",
    "    3. 一直递归，知道二分后两部分都有序，我们就进行并归\n",
    "    4. 并归=将两个小列表并为一个有序列表\n",
    "        - 归并操作每次从有序列表中取出最小值，放回初始列表（alist）。\n",
    "\n",
    "## 快速排序quickSort\n",
    "- 快速排序也采用分治策略，但不使用额外的存储空间。\n",
    "- 步骤\n",
    "    1. 按照某种规则确定基准值——【作用：帮助分割列表】\n",
    "    2. 初始化两个指标leftmark，rightmark【初始默认在列表左右，若与基准值重复，默认顺移下一位】\n",
    "    3. 以从左到右，逐步增加为排序目标\n",
    "    4. leftmark位置上与基准值比较，进行分区\n",
    "        - leftmark值<基准值时， leftmark右移，知道遇到leftmark值>基准值\n",
    "        - leftmark停止移动，换rightmark左移，知道遇到rightmark值<基准值\n",
    "        - rightmark停止移动后，将此时l与r两个数进行交换。\n",
    "        - ...重复上述流程，知道l与r相交。\n",
    "    5. 分区完成后，再对左右两部分进行进行快速排序【进行递归】\n",
    "    6. 如果列表的长度小于或等于1，说明它已经是有序列表；如果长度大于1，则进行分区操作并递归地排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8597625",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
